// 2025/11/20
// 数据流的中位数

class MedianFinder {
public:
    MedianFinder() {}
    
    void addNum(int num) {
        if(prev.size() == tail.size())
        {
            if(!tail.empty() && num > tail.top())
            {
                prev.emplace(tail.top());
                tail.pop();
                tail.emplace(num);
            }
            else
                prev.emplace(num);
        }
        else
        {
            if(!prev.empty() && num < prev.top())
            {
                tail.emplace(prev.top());
                prev.pop();
                prev.emplace(num);
            }
            else
                tail.emplace(num);
        }
    }
    
    double findMedian() {
        if(prev.size() > tail.size())
        {
            return prev.top();
        }
        else
        {
            return ((double)prev.top() + tail.top()) / 2;
        }
    }
    priority_queue<int, vector<int>, less<int>> prev;
    priority_queue<int, vector<int>, greater<int>> tail;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */